In recent years, with the practical use of cryptographic schemes based on pairing, studies to improve the pairing efficiency have become more active. The pairing is a two-input one-output bilinear function. The present cryptography uses a pairing that accepts as inputs two points P(x1, y1) and Q(x2, y2) on an elliptic curve defined on a finite field GF(pm) (x1, y1, x2, y2εGF(pm), p represents a prime number, and m represents an integer equal to or greater than 1) and returns an element ηT(P, Q) of an extension field GF(pd·m) of the finite field GF(pm) (ηT(P, Q)εGF(3d·m)):e(P(x1,y1),Q(x2,y2))→ηT(P,Q)  (1)
The first proposed algorithm for pairing calculation in polynomial time is the Miller algorithm for Tate pairing. Following the Miller algorithm, the ηT pairing algorithm, which is reduced by half in number of recursions compared with the Miller algorithm, and then the improved ηT pairing algorithm, which is further improved in calculation speed by omitting the cube root calculation involved with the ηT pairing algorithm, were proposed (see Non-patent literature 1, for example). In the following, the improved ηT pairing algorithm will be summarized.
<Improved ηT Pairing Calculation Algorithm>
[Preparation]
Eb: Eb represents a supersingular elliptic curve that is defined on a finite field GF(3m) and expressed as Y2=X3−X+b (bε{−1,1}).
σ: σ represents an indeterminate element that is a root of an irreducible polynomial σ2+1=0 over the finite field GF(3m).
ρ: ρ represents an indeterminate element that is a root of a polynomial ρ3−ρ−b=0 over the finite field GF(3m).
[Input] P(x1, y1), Q(x2, y2)(x1, y1, x2, y2εGF(3m))
[Output] ηT(P, Q)εGF(36m)
[Calculation Process]
Step 1: y1=−y1εGF(3m) (only if b=1)
Step 2: u=x1+x2+bεGF(3m)
Step 3: c=b
Step 4: f=−y1·u+y2·σ+y1·ρεGF(36m)
Step 5: repeat Steps 5-1 to 5-8 while increasing j from 0 to (m−1)/2 in increments of 1
Step 5-1: u=x1+x2+cεGF(3m)
Step 5-2: g=−u2+y1·y2·σ−u·ρ−ρ2εGF(36m)
Step 5-3: f=f·gεGF(36m)
Step 5-4: f=f3εGF(36m)
Step 5-5: y1=−y1εGF(3m)
Step 5-6: x2=x29εGF(3m)
Step 5-7: y2=y29εGF(3m)
Step 5-8: c=(c−b)mod 3εGF(3)
Step 6: output ffinalpowεGF(36m)[finalpow=(33m−1)(3m+1)(3m−3(m+1)/2+1)]
Non-patent literature 2 discloses an algorithm that is obtained by applying the loop unrolling technique, which is a kind of loop transformation, to the ηT pairing calculation. The loop unrolling technique is to improve the execution speed by decreasing the number of determination steps for loop termination, which occur in every repeated loop. According to the method disclosed in Non-patent literature 2, a processing that involves two loops according to the basic algorithm is performed in one loop to reduce the number of loop repetitions by half, thereby reducing the number of determination steps for loop termination by half.